{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #全排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #backtracking"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #回溯"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: permute"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #全排列"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定一个不含重复数字的整数数组 <code>nums</code> ，返回其 <strong>所有可能的全排列</strong> 。可以 <strong>按任意顺序</strong> 返回答案。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1,2,3]\n",
    "<strong>输出：</strong>[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [0,1]\n",
    "<strong>输出：</strong>[[0,1],[1,0]]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>nums = [1]\n",
    "<strong>输出：</strong>[[1]]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= nums.length &lt;= 6</code></li>\n",
    "\t<li><code>-10 &lt;= nums[i] &lt;= 10</code></li>\n",
    "\t<li><code>nums</code> 中的所有整数 <strong>互不相同</strong></li>\n",
    "</ul>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><meta charset=\"UTF-8\" />注意：本题与主站 46&nbsp;题相同：<a href=\"https://leetcode-cn.com/problems/permutations/\">https://leetcode-cn.com/problems/permutations/</a>&nbsp;</p>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [VvJkup](https://leetcode.cn/problems/VvJkup/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [VvJkup](https://leetcode.cn/problems/VvJkup/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3]', '[0,1]', '[1]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        rsSet = [[nums[0]]]\n",
    "        nums = nums[1:]\n",
    "        while len(nums)!=0:\n",
    "            numberOfPop = len(rsSet)\n",
    "            nextNum = nums.pop(0)\n",
    "            while numberOfPop > 0:\n",
    "                numberOfPop -=1\n",
    "                itemToWork = rsSet.pop(0)\n",
    "                for i in range(len(itemToWork)+1):\n",
    "                    newItem = itemToWork[:i] + [nextNum] + itemToWork[i:]\n",
    "                    rsSet.append(newItem)\n",
    "        return rsSet"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(track,nums):\n",
    "            if len(track)==n:\n",
    "                res.append(track[:])\n",
    "                return \n",
    "\n",
    "            for i in nums:\n",
    "                if i in track:\n",
    "                    continue\n",
    "                track.append(i)\n",
    "                backtrack(track,nums)\n",
    "                track.pop()\n",
    "\n",
    "        n = len(nums)\n",
    "        track,res = [],[]\n",
    "        backtrack(track,nums)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(result, res , choose):\n",
    "            if len(choose) == 0:\n",
    "                res.append(list(result))\n",
    "                return\n",
    "            for i in range(len(choose)):\n",
    "                result.append(choose[i])\n",
    "                key = choose.pop(i)\n",
    "                backtrack(result, res, choose)\n",
    "                result.pop()\n",
    "                choose.insert(i, key)\n",
    "        res = []\n",
    "        backtrack([], res, nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(result, res , choose):\n",
    "            if len(choose) == 0:\n",
    "                res.append(list(result))\n",
    "                return\n",
    "            for i in range(len(choose)):\n",
    "                result.append(choose[i])\n",
    "                key = choose.pop(i)\n",
    "                backtrack(result, res, choose)\n",
    "                result.pop()\n",
    "                choose.insert(i, key)\n",
    "        res = []\n",
    "        backtrack([], res, nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        for i in permutations(nums, len(nums)):\n",
    "            res.append(list(i))\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        track = []\n",
    "        used = [False]*len(nums)\n",
    "\n",
    "        self.backtrack(nums, used, track)\n",
    "        return self.res\n",
    "\n",
    "    def backtrack(self, nums, used, track):\n",
    "        #终止条件\n",
    "        if len(track)==len(nums):\n",
    "            self.res.append(track[:])\n",
    "            return\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            #判断不合法的 即已使用过的节点\n",
    "            if used[i]:\n",
    "                continue\n",
    "\n",
    "            #做选择\n",
    "            track.append(nums[i])\n",
    "            used[i]=True\n",
    "            #进入下一层决策树\n",
    "            self.backtrack(nums, used, track)\n",
    "            #撤销选择\n",
    "            track.pop()\n",
    "            used[i]=False\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(result, res , choose):\n",
    "            if len(choose) == 0:\n",
    "                res.append(list(result))\n",
    "                return\n",
    "            for i in range(len(choose)):\n",
    "                result.append(choose[i])\n",
    "                key = choose.pop(i)\n",
    "                backtrack(result, res, choose)\n",
    "                result.pop()\n",
    "                choose.insert(i, key)\n",
    "        res = []\n",
    "        backtrack([], res, nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(itertools.permutations(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(itertools.permutations(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        # python全排列的接口\n",
    "        # return list(itertools.permutations(nums))\n",
    "\n",
    "        # 返回相同元素的数组，顺序不同\n",
    "        def dfs(x):\n",
    "            if x==len(nums)-1:\n",
    "                res.append(list(nums))\n",
    "                return res\n",
    "\n",
    "            for i in range(x,len(nums)):\n",
    "                nums[i],nums[x] = nums[x],nums[i] # 交换，并先固定nums[x]\n",
    "                dfs(x+1) # 对下一位进行交换\n",
    "                nums[x],nums[i] = nums[i],nums[x]# 恢复交换\n",
    "        res = []\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        # print(nums[:1]+nums[1+1:])\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return [nums]\n",
    "        ret = []\n",
    "        for i in range(n):\n",
    "            tmp = [nums[i]]\n",
    "            for sub in self.permute(nums[:i]+nums[i+1:]):\n",
    "                # # print(type(tmp),type(sub))\n",
    "                # print(tmp, sub)\n",
    "                ret.append(tmp[:]+sub[:])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        def backtrack(first = 0):\n",
    "            # 所有数都填完了\n",
    "            if first == n:  \n",
    "                res.append(nums[:])\n",
    "            for i in range(first, n):\n",
    "                # 动态维护数组\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "                # 继续递归填下一个数\n",
    "                backtrack(first + 1)\n",
    "                # 撤销操作\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        backtrack()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(p for p in permutations(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        def dfs(ll):\n",
    "            if len(ll) == 1:\n",
    "                return [ll]\n",
    "            else:\n",
    "                last = ll[-1]\n",
    "                tmp_ret = dfs(ll[:-1])\n",
    "                ret = []\n",
    "                for item in tmp_ret:\n",
    "                    for i in range(len(item)+1):\n",
    "                        ret.append(item[:i]+[last]+item[i:])\n",
    "                    # ret.append(item+[last])\n",
    "                return ret\n",
    "\n",
    "        return dfs(nums)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        visited = [False] * len(nums)\n",
    "        path = []\n",
    "        result = []\n",
    "        def dfs(path,deep,visited):\n",
    "            if deep == len(nums):\n",
    "                result.append(path[:])\n",
    "            for i in range(len(nums)):\n",
    "                if visited[i] == False:\n",
    "                    path.append(nums[i])\n",
    "                    visited[i] = True\n",
    "                    dfs(path,deep+1,visited)\n",
    "                    path.pop()\n",
    "                    visited[i] = False\n",
    "        dfs(path,0,visited)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.res = []\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        used = [False]*len(nums)\n",
    "        track = []\n",
    "        self.backtrack(nums, track, used)\n",
    "        return self.res\n",
    "    def backtrack(self,nums: List[int], track: List[int], used: List[bool]) -> None:\n",
    "        if len(track) == len(nums):\n",
    "            self.res.append(track[:])\n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            used[i] = True\n",
    "            track.append(nums[i])\n",
    "            self.backtrack(nums, track, used)\n",
    "            used[i] = False\n",
    "            track.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.track = []\n",
    "        self.rst = []\n",
    "\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        used = [0] * len(nums)\n",
    "        self.backtrack(nums, used)\n",
    "        return self.rst\n",
    "    \n",
    "    def backtrack(self, nums, used):\n",
    "        if len(self.track) == len(nums):\n",
    "            self.rst.append(self.track[:])\n",
    "            return \n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            used[i] = 1\n",
    "            self.track.append(nums[i])\n",
    "            self.backtrack(nums, used)\n",
    "            self.track.pop()\n",
    "            used[i] = 0\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        global ans\n",
    "        ans=[]\n",
    "        self.recur(nums,[])\n",
    "        return ans\n",
    "    def recur(self,other,cur):\n",
    "        if len(other) == 0:\n",
    "            ans.append(cur)\n",
    "        for i in range(len(other)):\n",
    "            self.recur(other[:i]+other[i+1:],cur+[other[i]])\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        length = len(nums)\n",
    "        used = [False] * length\n",
    "        res = []\n",
    "\n",
    "        def dfs(nums, used, length, depth, res, path):\n",
    "            if depth == length:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(length):\n",
    "                if not used[i]:\n",
    "                    used[i] = True\n",
    "                    path.append(nums[i])\n",
    "                    dfs(nums, used, length, depth+1, res, path)\n",
    "                    used[i] = False\n",
    "                    path.pop()\n",
    "        if length == 0:\n",
    "            return []\n",
    "        dfs(nums, used, length, 0, res, [])\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        n = len(nums)\n",
    "        set_nums = set(nums)\n",
    "        def dfs(i,s):\n",
    "            if i == n:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for j in s:\n",
    "                path.append(j)\n",
    "                dfs(i+1,s-{j})\n",
    "                path.pop()\n",
    "        dfs(0,set_nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.rst  = []\n",
    "        self.track = []\n",
    "\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        used = [0] * len(nums)\n",
    "        self.backtrack(nums, used)\n",
    "        return self.rst\n",
    "    \n",
    "    def backtrack(self, nums, used):\n",
    "        if len(self.track) == len(nums):\n",
    "            self.rst.append(self.track[:])\n",
    "            return \n",
    "        \n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            used[i] = 1\n",
    "            self.track.append(nums[i])\n",
    "            self.backtrack(nums, used)\n",
    "            self.track.pop()\n",
    "            used[i] = 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def process(self, k):\n",
    "        if k >= self.length:\n",
    "            self.result.append(self.tmp[:])\n",
    "            return\n",
    "        for i in range(self.length):\n",
    "            if self.used[i]:\n",
    "                continue\n",
    "            self.used[i] = True\n",
    "            self.tmp.append(self.nums[i])\n",
    "            self.process(k+1)\n",
    "            self.used[i] = False\n",
    "            self.tmp.pop()\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.length = len(nums)\n",
    "        self.nums = nums\n",
    "        self.used = []\n",
    "        self.result = []\n",
    "        self.tmp = []\n",
    "\n",
    "        for i in range(self.length):\n",
    "            self.used.append(False)\n",
    "\n",
    "        self.process(0)\n",
    "\n",
    "        return self.result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def helper(cur, other):\n",
    "            if len(other) == 0:\n",
    "                ans.append(cur)\n",
    "            for i in range(len(other)):\n",
    "                helper(cur+[other[i]], other[:i]+other[i+1:])\n",
    "        \n",
    "        ans = []\n",
    "        helper([], nums)\n",
    "        return ans \n",
    "\n",
    "        '''\n",
    "        ans=[]\n",
    "        self.recur(nums,[])\n",
    "        return ans\n",
    "    def recur(self,other,cur):\n",
    "        if len(other) == 0:\n",
    "            ans.append(cur)\n",
    "        for i in range(len(other)):\n",
    "            self.recur(cur+[other[i]],other[:i]+other[i+1:])\n",
    "            '''\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def subfunc(self, nums, left, right, results):\n",
    "        if right - left <= 1:\n",
    "            permutation = nums[:]\n",
    "            results.append(permutation)          \n",
    "            return\n",
    "        for i in range(left, right):\n",
    "            nums[left], nums[i] = nums[i], nums[left]\n",
    "            self.subfunc(nums, left + 1, right, results)\n",
    "            nums[i], nums[left] = nums[left], nums[i]\n",
    "    \t\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        if n == 1:\n",
    "            return [nums]\n",
    "        results = []\n",
    "        self.subfunc(nums, 0, n, results)\n",
    "\n",
    "        return results"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) == 0: return []\n",
    "        if len(nums) == 1: return [nums]\n",
    "        res = []\n",
    "        for i in range(len(nums)):\n",
    "            flag = nums[:i] + nums[i+1:]\n",
    "            for j in self.permute(flag):\n",
    "                res.append([nums[i]] + j)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(itertools.permutations(nums))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        visited = [False] * n\n",
    "        trace = []\n",
    "        ans = []\n",
    "        self.dfs(nums, visited, trace, ans)\n",
    "        return ans\n",
    "\n",
    "    def dfs(self, nums, visited, trace, ans):\n",
    "        if len(trace) == len(nums):\n",
    "            ans.append(trace[:])\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if not visited[i]:\n",
    "                trace.append(nums[i])\n",
    "                visited[i] = True\n",
    "                self.dfs(nums, visited, trace, ans)\n",
    "                trace.pop()\n",
    "                visited[i] = False\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.result = []\n",
    "        self.handle(nums,0)\n",
    "        return self.result\n",
    "    def handle(self,nums,start):\n",
    "        if start >= len(nums):\n",
    "            self.result.append(nums.copy())\n",
    "            return\n",
    "        for index in range(start,len(nums)):\n",
    "            # swap value\n",
    "            nums[index], nums[start] = nums[start], nums[index]\n",
    "            self.handle(nums,start+1)\n",
    "            # recover value\n",
    "            nums[index], nums[start] = nums[start], nums[index]\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res = []\n",
    "        path = []\n",
    "        mark = [0 for i in range(n)]\n",
    "\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                return res.append(path[:])\n",
    "            for i in range(n):\n",
    "                if mark[i] == 0:\n",
    "                    path.append(nums[i])\n",
    "                    mark[i] = 1\n",
    "                    dfs()\n",
    "                    mark[i] = 0\n",
    "                    path.pop()\n",
    "\n",
    "\n",
    "        dfs()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def recur(nums):\n",
    "            if len(nums) <= 1: return [nums]\n",
    "            sub = recur(nums[1:])\n",
    "            ans = []\n",
    "            for sublist in sub:\n",
    "                for i in range(len(sublist)+1):\n",
    "                    ans.append(sublist[:i] + [nums[0]] + sublist[i:])\n",
    "            return ans\n",
    "        return recur(nums)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans,res = [],[]\n",
    "        def track(i,ans,res):\n",
    "            if i == n:\n",
    "                res.append(ans[:])\n",
    "                return\n",
    "            for j in nums:\n",
    "                if j not in ans:\n",
    "                    ans.append(j)\n",
    "                    track(i+1,ans,res)\n",
    "                    ans.pop()\n",
    "        track(0,ans,res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        n = len(nums)\n",
    "        def recur(index):\n",
    "            if index >= n:\n",
    "                ans.append(nums[:])\n",
    "                return\n",
    "            for i in range(index, n):\n",
    "                nums[i], nums[index] = nums[index], nums[i]\n",
    "                recur(index + 1)\n",
    "                nums[i], nums[index] = nums[index], nums[i]\n",
    "            return\n",
    "        recur(0)\n",
    "        return ans\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(list(x) for x in itertools.permutations(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def f(i,nums,ans):\n",
    "            if i==len(nums):\n",
    "                ans.append(nums.copy())\n",
    "            else:\n",
    "                for j in range(i,len(nums)):\n",
    "                    nums[i],nums[j] = nums[j],nums[i]\n",
    "                    f(i+1,nums,ans)\n",
    "                    nums[i],nums[j] = nums[j],nums[i]\n",
    "\n",
    "        ans = []\n",
    "        f(0,nums,ans)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(i):\n",
    "            if i == n:\n",
    "                rs.append(nums[:])\n",
    "\n",
    "            for j in range(i, n):\n",
    "                if i != j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "\n",
    "                backtrack(i + 1)\n",
    "\n",
    "                # undo\n",
    "                if i != j:\n",
    "                    nums[i], nums[j] = nums[j], nums[i]\n",
    "            \n",
    "\n",
    "        n = len(nums)\n",
    "        rs = []\n",
    "        backtrack(0)\n",
    "        return rs"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        visited = [False] * len(nums)\n",
    "        path = []\n",
    "        result = []\n",
    "        def dfs(path,deep,visited):\n",
    "            if deep == len(nums):\n",
    "                result.append(path[:])\n",
    "            for i in range(len(nums)):\n",
    "                if visited[i] == False:\n",
    "                    path.append(nums[i])\n",
    "                    visited[i] = True\n",
    "                    dfs(path,deep+1,visited)\n",
    "                    path.pop()\n",
    "                    visited[i] = False\n",
    "        dfs(path,0,visited)\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        if len(nums) >= 1:\n",
    "            self.permute_core([], nums, res)\n",
    "        return res\n",
    "    \n",
    "    def permute_core(self, before, nums, res):\n",
    "        if len(nums) <= 1:\n",
    "            res.append(before + nums)\n",
    "        else:\n",
    "            for i in range(len(nums)):\n",
    "                self.permute_core(before + [nums[i]], nums[:i] + nums[i+1:], res)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "        path = []\n",
    "        n=len(nums)\n",
    "\n",
    "        def dfs(i,s):\n",
    "            if i== n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for x in s:\n",
    "                path.append(x)\n",
    "                dfs(i+1,s-{x})\n",
    "                path.pop()\n",
    "            \n",
    "        dfs(0,set(nums))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        def backtrack(first = 0):\n",
    "            # if all integers are used up\n",
    "            if first == n:  \n",
    "                ans.append(nums[:])\n",
    "            for i in range(first, n):\n",
    "                # place i-th integer first \n",
    "                # in the current permutation\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "                # use next integers to complete the permutations\n",
    "                backtrack(first + 1)\n",
    "                # backtrack\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "        \n",
    "        backtrack()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        lsitlen = len(nums)\n",
    "        path = [0] *lsitlen\n",
    "        path_on = [False] *lsitlen\n",
    "        def TraceBack(n:int):\n",
    "            if n == lsitlen:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for index,elem in enumerate(path_on):\n",
    "                if not elem:\n",
    "                    path[n] = nums[index]\n",
    "                    path_on[index] = True\n",
    "                    TraceBack(n+1)\n",
    "                    path_on[index] = False\n",
    "        res = []      \n",
    "        TraceBack(0)\n",
    "        return res\n",
    "        \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(itertools.permutations(nums))\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        \n",
    "        n = len(nums)\n",
    "        res = []\n",
    "\n",
    "        def back(index):\n",
    "            if index == n:\n",
    "                res.append(nums[:])\n",
    "            \n",
    "            for k in range(index, n):\n",
    "                nums[index], nums[k] = nums[k], nums[index]\n",
    "                back(index+1)\n",
    "                nums[index], nums[k] = nums[k], nums[index]\n",
    "\n",
    "        back(index=0)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.res = []\n",
    "        path = []\n",
    "        vis = [False] * (len(nums))\n",
    "\n",
    "        def dfs():\n",
    "            if len(path) == len(nums):\n",
    "                self.res.append(path[:])\n",
    "                return\n",
    "\n",
    "            for i in range(len(nums)):\n",
    "                if not vis[i]:\n",
    "                    path.append(nums[i])\n",
    "                    vis[i] = True\n",
    "                    dfs()\n",
    "                    path.pop()\n",
    "                    vis[i] = False\n",
    "                else:\n",
    "                    continue\n",
    "        dfs()\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 对位置进行回溯\n",
    "        self.nums = nums\n",
    "        candidate = [None]*len(nums)\n",
    "        self.ans = []\n",
    "        self.backTrack(0, candidate)\n",
    "        return self.ans\n",
    "\n",
    "    \n",
    "    def backTrack(self, start, candidate):\n",
    "        if start == len(self.nums):\n",
    "            self.ans.append(candidate.copy())\n",
    "        else:\n",
    "            for i in range(len(candidate)):\n",
    "                if candidate[i] is not None:\n",
    "                    continue\n",
    "                candidate[i] = self.nums[start]\n",
    "                self.backTrack(start + 1, candidate)\n",
    "                candidate[i] = None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans = []\n",
    "        path = [0] * n\n",
    "\n",
    "        def dfs(depth: int, rest: set[int]):\n",
    "            if depth == n:\n",
    "                ans.append(path[:])\n",
    "                return\n",
    "            for x in rest:\n",
    "                path[depth] = x\n",
    "                dfs(depth + 1, rest - {x})\n",
    "\n",
    "        dfs(0, set(nums))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        aaa = res.copy()\n",
    "        for i in nums:\n",
    "            for temp in aaa:\n",
    "                for j in range(len(temp)+1):\n",
    "                    w = temp.copy()\n",
    "                    w.insert(j, i)\n",
    "                    res.append(w)\n",
    "                res.remove(temp)\n",
    "            aaa = res.copy()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        path = []\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        def dfs(depth):\n",
    "            if depth == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if nums[i] in path:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                dfs(depth+1)\n",
    "                path.pop()\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        path = []\n",
    "        ret = []\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                ret.append([val for val in path])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if nums[i] in path:continue\n",
    "                path.append(nums[i])\n",
    "                dfs()\n",
    "                path.remove(nums[i])\n",
    "        dfs()\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(itertools.permutations(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self, nums, path, result, used):\n",
    "        if len(path) == len(nums):\n",
    "            result.append(path[:])\n",
    "            return\n",
    "\n",
    "        for i in range(len(nums)):\n",
    "            if used[i] == True:\n",
    "                continue\n",
    "            path.append(nums[i])\n",
    "            used[i] = True\n",
    "            self.backtracking(nums, path, result, used)\n",
    "            path.pop()\n",
    "            used[i] = False\n",
    "\n",
    "    def permute(self, nums):\n",
    "        result = []\n",
    "        used = [False] * len(nums)\n",
    "        self.backtracking(nums, [], result, used)\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "\n",
    "        res, path = [], []\n",
    "\n",
    "        def dfs(path, s):\n",
    "            if s == len(nums):\n",
    "                res.append(nums[:])\n",
    "                return\n",
    "            for i in range(s, len(nums)):\n",
    "                nums[s], nums[i] = nums[i], nums[s]\n",
    "                dfs(path + [nums[i]], s + 1)\n",
    "                nums[s], nums[i] = nums[i], nums[s]\n",
    "\n",
    "        dfs(path, 0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:  \n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        result = []\n",
    "        track = []\n",
    "        used = [False for i in range(len(nums))]\n",
    "        def backtrack(nums):\n",
    "            if len(track) == len(nums):\n",
    "                result.append(track.copy())\n",
    "            for i in range(len(nums)):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                used[i] = True\n",
    "                track.append(nums[i])\n",
    "\n",
    "                backtrack(nums)\n",
    "\n",
    "                track.pop(-1)\n",
    "                used[i] = False\n",
    "        backtrack(nums)\n",
    "        return result\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        return list(itertools.permutations(nums))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) == 1:\n",
    "            return [nums]\n",
    "        elif len(nums) == 2:\n",
    "            return [[nums[0],nums[1]], [nums[1],nums[0]]]\n",
    "\n",
    "        return [[nums[x]] + y for x in range(len(nums)) for y in self.permute(nums[:x] + nums[x+1:])]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        final = []\n",
    "        path = []\n",
    "\n",
    "        def backtrack(n):\n",
    "            if n == len(nums):\n",
    "                final.append(path[:])\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                if nums[i] not in path:\n",
    "                    path.append(nums[i])\n",
    "                    backtrack(n + 1)\n",
    "                    path.pop()\n",
    "        \n",
    "        backtrack(0)\n",
    "        return final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        ans = []\n",
    "\n",
    "        def _helper(nums, sub):\n",
    "            nonlocal ans\n",
    "            if not nums:\n",
    "                ans.append(sub)\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                num = nums[i]\n",
    "                _helper(nums[:i] + nums[i+1:], sub + [num])\n",
    "        \n",
    "        _helper(nums, [])\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res, path, used = [], [], [False] * n\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                res.append(path[:])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                dfs()\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        dfs()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 对位置进行回溯\n",
    "        self.nums = nums\n",
    "        candidate = [None]*len(nums)\n",
    "        self.ans = []\n",
    "        self.backTrack(0, candidate)\n",
    "        return self.ans\n",
    "\n",
    "    \n",
    "    def backTrack(self, start, candidate):\n",
    "        if start == len(self.nums):\n",
    "            self.ans.append(candidate.copy())\n",
    "        else:\n",
    "            for i in range(len(candidate)):\n",
    "                if candidate[i] is not None:\n",
    "                    continue\n",
    "                candidate[i] = self.nums[start]\n",
    "                self.backTrack(start + 1, candidate)\n",
    "                candidate[i] = None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def backtracking(self, nums, path, res):\n",
    "        if len(path) == len(nums):\n",
    "            res.append(path[:])\n",
    "        \n",
    "        # 单层逻辑\n",
    "        for i in nums:\n",
    "            if i not in path:\n",
    "                path.append(i)\n",
    "                self.backtracking(nums, path, res)\n",
    "                path.pop(-1)\n",
    "            else:\n",
    "                continue\n",
    "\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        path = []\n",
    "        self.backtracking(nums, path, res)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 对位置进行回溯\n",
    "        self.nums = nums\n",
    "        candidate = [None]*len(nums)\n",
    "        self.ans = []\n",
    "        self.backTrack(0, candidate)\n",
    "        return self.ans\n",
    "\n",
    "    \n",
    "    def backTrack(self, start, candidate):\n",
    "        if start == len(self.nums):\n",
    "            self.ans.append(candidate.copy())\n",
    "        else:\n",
    "            for i in range(len(candidate)):\n",
    "                if candidate[i] is  None:\n",
    "                    candidate[i] = self.nums[start]\n",
    "                    self.backTrack(start + 1, candidate)\n",
    "                    candidate[i] = None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.res=[]\n",
    "        used=[False]*len(nums)\n",
    "        self.recur(nums,[],used)\n",
    "        return self.res\n",
    "\n",
    "    def recur(self,nums,track,used):\n",
    "        if len(track)==len(nums):\n",
    "            self.res.append(track.copy())\n",
    "            return\n",
    "        for i in range(len(nums)):\n",
    "            if used[i]:\n",
    "                continue\n",
    "            used[i]=True\n",
    "            track.append(nums[i])\n",
    "            self.recur(nums,track,used)\n",
    "            track.pop()\n",
    "            used[i]=False"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        if len(nums) == 0:\n",
    "            return []\n",
    "\n",
    "        result = []\n",
    "        cur_list = []\n",
    "        self.dfs(result, cur_list, nums)\n",
    "        return result\n",
    "\n",
    "    def dfs(self, result, cur_list, nums):\n",
    "        if len(cur_list) == len(nums):\n",
    "            result.append(cur_list.copy())\n",
    "\n",
    "        for i in range(0, len(nums)):\n",
    "            if nums[i] in cur_list:\n",
    "                continue\n",
    "            cur_list.append(nums[i])\n",
    "            self.dfs(result, cur_list, nums)\n",
    "            cur_list.pop()\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        visited = [False] * n\n",
    "        tmp = [0] * n\n",
    "        res = []\n",
    "\n",
    "        def dfs(position):\n",
    "            if position == n:\n",
    "                res.append(tmp[:])\n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    visited[i] = True       \n",
    "                    tmp[position] = nums[i]\n",
    "                    dfs(position + 1)\n",
    "                    visited[i] = False\n",
    "        \n",
    "        dfs(0)\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        # 对位置进行回溯\n",
    "        self.nums = nums\n",
    "        candidate = [None]*len(nums)\n",
    "        self.ans = []\n",
    "        self.backTrack(0, candidate)\n",
    "        return self.ans\n",
    "\n",
    "    \n",
    "    def backTrack(self, start, candidate):\n",
    "        if start == len(self.nums):\n",
    "            self.ans.append(candidate.copy())\n",
    "        else:\n",
    "            for i in range(len(candidate)):\n",
    "                if candidate[i] is not None:\n",
    "                    continue\n",
    "                candidate[i] = self.nums[start]\n",
    "                self.backTrack(start + 1, candidate)\n",
    "                candidate[i] = None\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = [[]]\n",
    "        aaa = res.copy()\n",
    "        for i in nums:\n",
    "            for temp in aaa:\n",
    "                for j in range(len(temp)+1):\n",
    "                    w = temp.copy()\n",
    "                    w.insert(j, i)\n",
    "                    res.append(w)\n",
    "                res.remove(temp)\n",
    "            aaa = res.copy()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        l = len(nums)\n",
    "        d = dict()\n",
    "        ans = []\n",
    "        def Find(li, n):\n",
    "            if n == l:\n",
    "                ans.append(li.copy())\n",
    "                return\n",
    "            for x in nums:\n",
    "                if d.get(x, -1) == -1:\n",
    "                    d[x] = 1\n",
    "                    li.append(x)\n",
    "                    Find(li, n + 1)\n",
    "                    d[x] = -1\n",
    "                    li.pop()\n",
    "        Find([], 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        self.st = [False for _ in range(len(nums))]\n",
    "        self.final = []\n",
    "\n",
    "        def backtrack(path, n):\n",
    "            if n == len(nums):\n",
    "                self.final.append(path[:])\n",
    "            \n",
    "            for i in range(len(nums)):\n",
    "                if not self.st[i]:\n",
    "                    self.st[i] = True\n",
    "                    path[n] = nums[i]\n",
    "                    backtrack(path, n + 1)\n",
    "                    self.st[i] = False\n",
    "        \n",
    "        backtrack([0 for _ in range(len(nums))], 0)\n",
    "        return self.final"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res,path,used = [],[],[False]*n\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                res.append(path[:]) # 内部可能需要将各个字符都加入\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i]:continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                dfs()\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        dfs()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        ans, curr = [], []\n",
    "        mask = 0\n",
    "        def backtrace():\n",
    "            nonlocal mask\n",
    "            if len(curr) == n:\n",
    "                ans.append(curr[:])\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if mask & (1 << i) == 0:\n",
    "                    mask |= 1 << i\n",
    "                    curr.append(nums[i])\n",
    "                    backtrace()\n",
    "                    mask &= ~(1 << i)\n",
    "                    curr.pop()\n",
    "\n",
    "        backtrace()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        def backtrack(first=0):\n",
    "            if first == n:\n",
    "                res.append(nums[:])\n",
    "            for i in range(first, n):\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "                backtrack(first + 1)\n",
    "                nums[first], nums[i] = nums[i], nums[first]\n",
    "        n = len(nums)\n",
    "\n",
    "        res = []\n",
    "        backtrack()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res=[]\n",
    "        def dfs(path,nums,used):\n",
    "            if len(path)==len(nums):\n",
    "                res.append(path[:])\n",
    "            for i in range(len(nums)):\n",
    "                if used[i]:\n",
    "                    continue\n",
    "                used[i]=True\n",
    "                path.append(nums[i])\n",
    "                dfs(path,nums,used)\n",
    "                path.pop()\n",
    "                used[i]=False\n",
    "        used=[False for _ in range(len(nums))]\n",
    "        dfs([],nums,used)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        path = []\n",
    "        res = []\n",
    "        used = [0] * n\n",
    "        # nums = sorted(nums)\n",
    "        def backtracking(nums):\n",
    "            if len(path) == n:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i] == 0:\n",
    "                    path.append(nums[i])\n",
    "                    used[i] = 1\n",
    "                    backtracking(nums)\n",
    "                    used[i] = 0\n",
    "                    path.pop()\n",
    "        backtracking(nums)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        res,path,used = [],[],[False]*n\n",
    "        def dfs():\n",
    "            if len(path) == n:\n",
    "                res.append(path[:]) # 内部可能需要将各个字符都加入\n",
    "                return\n",
    "            for i in range(n):\n",
    "                if used[i]:continue\n",
    "                path.append(nums[i])\n",
    "                used[i] = True\n",
    "                dfs()\n",
    "                path.pop()\n",
    "                used[i] = False\n",
    "        dfs()\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        n = len(nums)\n",
    "        path = [0] * n\n",
    "        on_path = [False] * n \n",
    "        res = []\n",
    "        def dfs(i):\n",
    "            if i == n:\n",
    "                res.append(path.copy())\n",
    "                return\n",
    "            for j in range(n):\n",
    "                if not on_path[j]:\n",
    "                    path[i] = nums[j]\n",
    "                    on_path[j] = True\n",
    "                    dfs(i + 1)\n",
    "                    on_path[j] = False\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def permute(self, nums: List[int]) -> List[List[int]]:\n",
    "        res = []\n",
    "        n = len(nums)\n",
    "        path = [0]*n\n",
    "        used = [False]*n\n",
    "\n",
    "        def dfs(u):\n",
    "            if u==n:\n",
    "                res.append(path.copy())\n",
    "                return \n",
    "            for i in range(n):\n",
    "                if not used[i]:\n",
    "                    path[u] = nums[i]\n",
    "                    used[i]=True\n",
    "                    dfs(u+1)\n",
    "                    used[i]=False\n",
    "        dfs(0)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution(object):\n",
    "    def permute(self, nums):\n",
    "        \"\"\"\n",
    "        :type nums: List[int]\n",
    "        :rtype: List[List[int]]\n",
    "        \"\"\"\n",
    "        n = len(nums)\n",
    "        visited = [False] * n\n",
    "        temp = [0] * n\n",
    "        res = []\n",
    "        \n",
    "        # 深度优先搜索\n",
    "        def dfs(position):\n",
    "            if position == n:\n",
    "                res.append(temp[:])\n",
    "                return \n",
    "            for i in range(n):\n",
    "                if not visited[i]:\n",
    "                    visited[i] = True\n",
    "                    temp[position] = nums[i]\n",
    "                    dfs(position+1)\n",
    "                    visited[i] = False\n",
    "        dfs(0)\n",
    "        return res "
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
